package listnode;


import listnode.data.ListNode;

/**
 * 合并 K 个升序链表
 *
 * 1.分治合并
 *
 * 2.优先队列
 */
public class MergeKLists1 {


    //[[1,4,5],[1,3,4],[2,6]]
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists,0,lists.length-1);
    }

    public ListNode merge(ListNode[] lists,int l,int r){
        if (l==r){
            //只有一个数组
            return lists[l];
        }
        if (l>r){
            return null;
        }
        int mid=(l+r)/2;
        return mergeTwoLists(merge(lists,l,mid),merge(lists,mid+1,r));
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode preHead=new ListNode(-1);
        ListNode pre=preHead;

        while (list1!=null&&list2!=null){
            if (list1.val<=list2.val){
                pre.next=list1;
                list1=list1.next;
            }else{
                pre.next=list2;
                list2=list2.next;
            }
            pre=pre.next;
        }

        pre.next=list1==null?list2:list1;

        return preHead.next;
    }




}
